package exam.dijkstra;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Scanner;

public class Dijkstra {

    public static HashMap<Node, Integer> dijkstra1(Node from, Node to) {
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        HashMap<Node, ArrayList<Node>> routeMap = new HashMap<>();
        distanceMap.put(from, 0);
        ArrayList<Node> nodes = new ArrayList<>();
        nodes.add(from);
        routeMap.put(from, nodes);
        // 打过对号的点
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            // 原始点 -> minNode(跳转点) 最小距离distance
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                    ArrayList<Node> routeNodes = new ArrayList<>();
                    routeNodes.addAll(routeMap.get(minNode));
                    routeNodes.add(toNode);
                    routeMap.put(toNode, routeNodes);
                } else { // toNode
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                    if (distance + edge.weight < distanceMap.get(toNode)) {
                        ArrayList<Node> routeNodes = new ArrayList<>();
                        routeNodes.addAll(routeMap.get(minNode));
                        routeNodes.add(toNode);
                        routeMap.put(toNode, routeNodes);
                    }
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
//        System.out.println(JSON.toJSONString(routeMap));
        ArrayList<Node> toMap = routeMap.get(to);
        for (Node node : toMap) {
            System.out.print(node.value + " ");
        }
        System.out.println();
        return distanceMap;
    }

    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    public static Graph createGraph(int[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            // 拿到每一条边， matrix[i]
            int weight = matrix[i][0];
            int from = matrix[i][1];
            int to = matrix[i][2];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String[] strings1 = str1.split(" ");
        int form = Integer.parseInt(strings1[0]);
        int to = Integer.parseInt(strings1[1]);
//        String s = scanner.nextLine();
		String s = "1-4,1-6,2-4,2-6,3-5,3-6,4-5,5-6";
        String[] strings = s.split(",");
        int[][] matrix = new int[strings.length * 2][3];
        for (int i = 0, j = 0; i < strings.length; i++, j++) {
            String[] arr = strings[i].split("-");
            int f = Integer.parseInt(arr[0]);
            int t = Integer.parseInt(arr[1]);
            matrix[j][0] = 1;
            matrix[j][1] = f;
            matrix[j][2] = t;
            j++;
            matrix[j][0] = 1;
            matrix[j][1] = t;
            matrix[j][2] = f;
        }

        Graph graph = createGraph(matrix);
        dijkstra1(graph.nodes.get(form), graph.nodes.get(to));
    }

}
